﻿
// Ahmad Salama & Amine Allaouchiche
//

#include "graphm.h"

//Constructor:-----------------------------------------------------------------
GraphM::GraphM()
{
	size = 0;
	this->data = NULL;
	this->C = NULL;
	this->T = NULL;
}

//Destructor:------------------------------------------------------------------
GraphM::~GraphM()
{
	delete [] data;	

	for(int i = 0; i < this->size; i++)
	{
		delete [] C[i];
		delete [] T[i];
	}
	delete [] C;
	delete [] T;
}

//buildGraph:------------------------------------------------------------------
void GraphM::buildGraph(ifstream& reader)
{
	this->data = new NodeData[this->size];
	if( !reader.eof())
	{
		int size;
		reader >> size;
		//Initilize data members:
		this->size = size + 1;

		//free resources before re-intilize:
		if(this->data != NULL)
		{
			delete [] this->data; 
		}
		this->data = new NodeData[this->size];

		//free resources before re-intilize:
		if(this->C != NULL)
		{
			for(int i = 0; i < this->size; i++)
			{
				delete [] C[i];				
			}
			delete [] C;			
		}
		this->C = new int*[this->size];

		//free resources before re-intilize:
		if(this->T != NULL)
		{
			for(int i = 0; i < this->size; i++)
			{				
				delete [] T[i];
			}			
			delete [] T;
		}
		this->T = new TableType*[this->size];

		C[0] = NULL; //Not used:
		T[0] = NULL; //Not used:

		for(int i = 1; i < this->size; i++)
		{
			C[i] = new int[this->size];
			T[i] = new TableType[this->size];

			for ( int j = 1; j < this->size; j++)
			{
				T[i][j].path = 0;
				T[i][j].visited = false;
				if( i == j)
				{
					C[i][j] = 0;
					T[i][j].dist = 0;					
				}
				else
				{
					C[i][j] = INT_MAX;
					T[i][j].dist = INT_MAX;					
				}
			}
		}		
		string s;
		getline (reader,s); // geting rid of the endl
		// // this loop reads the lines containing the nodes names
		
		for ( int i = 1; i <= size; i++)
		{
			getline (reader,s);			
			this->data[i] = NodeData(s);								
		}

		// this loop fills the graph paths with their weights
		int nodeIndex =  INT_MAX,endNode, weight ;
		reader >> nodeIndex >>endNode>> weight;
		// making sure the reader still has data
		while ( !reader.eof() && nodeIndex != 0)
		{			
			if ( (isOk (nodeIndex) &&  isOk (endNode)	&& weight >= 0) )
			{
				C[nodeIndex][endNode] = weight;
			}
			// reading the destination node and  the weight of the path
			reader >> nodeIndex >> endNode>> weight; 
		}	
	}	
}

// insertEdge -----------------------------------------------------------------
// creates or overwrites the edge cost from v to w
//  ---------------------------------------------------------------------------
const bool GraphM::insertEdge(const int source  , const int destination, const int weight)
{
	// data checking
	if(!(isOk (source) &&  isOk (destination)	&& (weight >= 0))) return false;
	C[source][destination] = weight;
	return true;
}

// removeEdge -----------------------------------------------------------------
// assign edge from v to w to weight = infinity
//  ---------------------------------------------------------------------------
const bool GraphM::removeEdge(const int source, const int destination)
{
	// data checking
	if(!(isOk (source) && isOk (destination))) return false;
	// delete the edge
	C[source][destination] = INT_MAX;
	return true;
}

//findShortestPath(): Overloaded-----------------------------------------------
void GraphM::findShortestPath()
{
	for(int i = 1; i < this->size; i++)
	{
		this->findShortestPath(i);		
	}
}

//findShortestPath(int):-------------------------------------------------------
void GraphM::findShortestPath(int seed)
{	
	int prevPath = seed;
	bool changed = false;
	for( ; ; )
	{
		//Find v:
		int v_Index = findShortest(seed, prevPath);

		// -1 indicates that there are no more adjacents to go over; break.
		if(v_Index == -1)
		{
			break;
		}

		T[seed][v_Index].visited = true;		

		//for each w adjacent to v
		for(int target = 1; target < this->size; target++)
		{
			//T[w].dist = min(T[w].dist, T[v].dist + C[v][w])
			if(!T[v_Index][target].visited)
			{
				changed = false;
				T[seed][target].dist = calMin(T[seed][target].dist, T[seed][v_Index].dist + C[v_Index][target], changed);

				//if changed is true; set the path:
				if(changed)
				{
					T[seed][target].path = v_Index;
				}
			}
		}
	}
}

//findShortest:----------------------------------------------------------------
int GraphM::findShortest(int source, int & prev_path)
{
	int minValue = INT_MAX;
	int minIndex = -1;

	for(int t = 1; t < this->size; t++)
	{
		if(!T[source][t].visited)// && source != t)
		{
			if(T[source][t].dist < minValue)
			{
				minValue = T[source][t].dist;
				minIndex = t;			
			}
		}
	}
	return minIndex;
}

//calMin:----------------------------------------------------------------------
int GraphM::calMin(int a, int b, bool& changed)
{
	if( a <= b || b < 0)
	{

		return a;
	}
	changed = true;
	return b;
}

//calMin-----------------------------------------------------------------------
int GraphM::calMin(int a, int b)
{
	if( a <= b || b < 0)
	{
		return a;
	}
	return b;
}

//displayAll:------------------------------------------------------------------
void GraphM::displayAll()
{ 
	// (uses couts to demonstrate that the algorithm works properly as shown)
	cout << "| " << setw(20) << left << "Description"  << "| " << setw(5) << "From" << "| " << setw(5) 
		<< left << "To" << "| " << setw(10) << "Dijkstra's" << "| " << setw(20) << "Path" << endl;	
	cout << endl<<endl;

	for( int i = 1; i < this->size; i++ )
	{
		cout << "| " << setw(20) << data[i] << endl;

		for( int j = 1; j < size; j++ )
		{
			if( j != i )
			{				
				display (i,j);
			}
		}
		cout << endl;
	}
}

//display: --------------------------------------------------------------------
void GraphM::display(int v, int k)
{ 
	if ( isOk(v) && isOk(k) && (v != k))
	{
		string s = "---"; 

		if (T[v][k].path>0)
		{
			cout << "| " << setw(20) << "" << "| " << setw(5) << v << "| " << setw(5)
				<< k << "| " << setw(10) << T[v][k].dist << "| " << v;

			displayHelper(v,k);	
			cout << " " << k << endl;
		}
		else
		{
			cout << "| " << setw(20) << "" << "| " << setw(5) << v << "| " << setw(5)
				<< k << "| " << setw(10) << s << "| " << endl;	
		}
	}
}

//displayHelper:---------------------------------------------------------------
void GraphM::displayHelper(int v, int k)
{
	if(T[v][k].path == v)
		return;
	displayHelper(v, T[v][k].path);
	cout << "  " << T[v][k].path ;	
}

//isOk:------------------------------------------------------------------------
const bool GraphM::isOk( const int value)
{
	return (value <= size && value >= 1 );
}
